package leetcode.editor.cn;

/**
 * @author Administrator
 * @description
 * @date 2023/3/15 0015
 */
public class Solution1536 {

    public int minSwaps(int[][] grid) {
        int n = grid.length;
        // 列出右侧连续0的数量有效的
        int[] nums = new int[n];
        for (int i = 0, p = n - 1; i < n; i++, p--) {
            // 从后往前都是零才符合
            for (int j = n-1; j >=0 && grid[i][j] == 0; j--) {
                nums[p]++;
            }
        }
        int ans = 0;
        // i代表需要的零个数
        for (int i = n-1; i > 0; i--) {
            boolean ok = false;
            for (int j = i; j >= 0; j--) {
                if (nums[j] >= i) {
                    ans += i-j;
                    // 产生变动，移动其数组
                    for (int k = j; k < i; k++) {
                        nums[k] = nums[k + 1];
                    }
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                return -1;
            }
        }
        return ans;
    }
}
